package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * 897. 递增顺序查找树
 * @author feizns
 * @since 2020/1/6
 */
public class IncreasingBST {

    public static TreeNode increasingBST(TreeNode root) {
        if ( root != null ) {
            while ( root.left != null ) {
                if ( root.left.right != null )
                    root.left = leftRotate(root.left);
                root = rightRotate(root);
            }
            root.right = increasingBST(root.right);
        }
        return root;
    }

    private static TreeNode rightRotate(TreeNode node) {
        TreeNode left = node.left;
        node.left = left.right;
        left.right = node;
        return left;
    }

    private static TreeNode leftRotate(TreeNode node) {
        TreeNode right = node.right;
        node.right = right.left;
        right.left = node;
        return right;
    }

//    private static TreeNode create() {
//        TreeNode ret = new TreeNode();
//    }

}
